// 给你一个字符串 s ，请你根据下面的算法重新构造字符串：

// 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
// 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
// 重复步骤 2 ，直到你没法从 s 中选择字符。
// 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
// 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
// 重复步骤 5 ，直到你没法从 s 中选择字符。
// 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
// 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。

// 请你返回将 s 中字符重新排序后的 结果字符串 。


const sortString = function (s: string): string {
    let strSize: number = s.length;
    let res: string = ''; // 结果字符
    const hashMap = new Map<string, number>(); // 哈希表统计
    // 先用哈希表来统计词频
    for (let i = 0; i < s.length; i++) {
        const value: number = hashMap.has(s[i]) ? hashMap.get(s[i])! : 0;
        hashMap.set(s[i], value + 1);
    }
    const unicodeA: number = 'a'.charCodeAt(0);
    // 主逻辑循环，当字符串构造完成时结束
    while (res.length != strSize) {
        // 从字母'a'开始循环
        for (let i = unicodeA; i < unicodeA + 26; i++) {
            // 求出当前的字符并取出对应的哈希值
            const currStr: string = String.fromCharCode(i);
            const currVal: number | undefined = hashMap.get(currStr);
            if (currVal && currVal > 0) {
                res = res + currStr;
                hashMap.set(currStr, currVal - 1);
            }
        }
        // 从字母'z'开始倒序循环
        for (let i = unicodeA + 25; i >= unicodeA; i--) {
            // 求出当前的字符并取出对应的哈希值
            const currStr: string = String.fromCharCode(i);
            const currVal: number | undefined = hashMap.get(currStr);
            if (currVal && currVal > 0) {
                res = res + currStr;
                hashMap.set(currStr, currVal - 1);
            }
        }
    }
    return res;
};


// 这道题目看着比较复杂，但也是外强中干的一道题目
// 难点主要在于理解构造字符串的规则
// 为了避免反复的剪切字符串造成的开销与空间浪费，这里使用哈希表来记录每个字符出现的次数是比较合理的
// 主循环逻辑比较好确定，我们只要保证当前构造字符串的长度与原字符串的长度相等即可
// 这里比较难以想到的是怎么样保证每次挑的字符串顺序是升序且不保证重复
// 这里就利用了字符串一个非常方便的性质，即英文字母最多只有26个，它其实是一个天然的“字母桶”
// 我们按照字母表的顺序来正反遍历即可保证可以根据题目的要求
// 从左遍历取，就是从小到大，
// 从右遍历取，就是从大到小
// 这个遍历的过程作为次要循环写在主循环内
// 当走出主循环时，我们就完成了题目要求的排序。